#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef pair < int , int > pii;
typedef vector < int > vec;
typedef vector < pii > veg;
typedef long long ll;
typedef double db;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch =='-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}


const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int n,m,a[N],dfn[N],siz[N],f[N][2],top[N],son[N],tim,ind[N],edid[N];
int dep[N],fa[N];
vec G[N];

struct mat {
    int arr[2][2];
    mat() { arr[0][0] = arr[0][1] = arr[1][0] = arr[1][1] = -inf; }
    int* operator [] (int x) { return arr[x]; }
    const int * operator [] (int x) const { return arr[x]; }
    friend mat operator * (mat a,mat b) {
		mat c;
		for(int i = 0;i < 2;i++)
			for(int j = 0;j < 2;j++)
				for(int k = 0;k < 2;k++)
					c[i][k] = max(c[i][k],a[i][j] + b[j][k]);
		return c;
    }
} tval[N];

void dfs(int x,int p) {
    dep[x] = dep[p] + 1; fa[x] = p; siz[x] = 1;
    for(auto y : G[x]) if(y ^ p) dfs(y,x),siz[x] += siz[y],son[x] = siz[y] > siz[son[x]] ? y : son[x];
}

void dfs1(int x,int anc) {
    ind[dfn[x] = ++tim] = x; top[x] = anc; edid[anc] = tim;
    tval[x][0][0] = tval[x][0][1] = 0; tval[x][1][0] = a[x]; f[x][0] = 0; f[x][1] = a[x];
    if(son[x]) {
		dfs1(son[x],anc); 
		f[x][0] += max(f[son[x]][0],f[son[x]][1]); f[x][1] += f[son[x]][0];
    }
    for(auto y : G[x])
		if(y ^ fa[x] && y ^ son[x]) {
			dfs1(y,y);
			tval[x][0][0] += max(f[y][0],f[y][1]); tval[x][0][1] = tval[x][0][0];
			tval[x][1][0] += f[y][0];
			f[x][0] += max(f[y][0],f[y][1]); f[x][1] += f[y][0];
		}
}

namespace seg {
    mat val[N << 2];
    void pu(int o) { val[o] = val[o << 1] * val[o << 1 | 1]; }
    void build(int o = 1,int l = 1,int r = n) {
		if(l == r) return val[o] = tval[ind[l]],void(); int mid = l + r >> 1;
		build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); pu(o);
    }
    void upd(int pos,int o = 1,int l = 1,int r = n) {
		if(l == r) return val[o] = tval[ind[l]],void(); int mid = l + r >> 1;
		if(pos <= mid) upd(pos,o << 1,l,mid); else upd(pos,o << 1 | 1,mid + 1,r); pu(o);
    }
    mat query(int xl,int xr,int o = 1,int l = 1,int r = n) {
		if(l == xl && xr == r) return val[o]; int mid = l + r >> 1;
		if(xr <= mid) return query(xl,xr,o << 1,l,mid); else if(xl > mid) return query(xl,xr,o << 1 | 1,mid + 1,r);
		else return query(xl,mid,o << 1,l,mid) * query(mid + 1,xr,o << 1 | 1,mid + 1,r);
    }
    void modify(int x,int w) {
		int del = w - a[x]; tval[x][1][0] += del;
		while(x) {
			mat bef = query(dfn[top[x]],edid[top[x]]);
			upd(dfn[x]); mat aft = query(dfn[top[x]],edid[top[x]]);
			x = fa[top[x]];
			tval[x][0][0] += max(aft[0][0],aft[1][0]) - max(bef[0][0],bef[1][0]); tval[x][0][1] = tval[x][0][0];
			tval[x][1][0] += aft[0][0] - bef[0][0];
		}
    }
    int getans() {
		mat ans = query(dfn[1],edid[1]);
		return max(ans[0][0],ans[1][0]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin); freopen("P4719.out", "w", stdout);
#endif
    n = in,m = in; for(int i = 1;i <= n;i++) a[i] = in;
    for(int i = 1,u,v;i < n;i++) u = in,v = in,G[u].pb(v),G[v].pb(u);
    dfs(1,0); dfs1(1,1); seg :: build();
    while(m--) {
		int x = in,y = in;
		seg :: modify(x,y); a[x] = y;
		printf("%d\n",seg :: getans());
    } return 0;
}
